Thêm vào G {\displaystyle G} một đỉnh s {\displaystyle s} và với mỗi x ∈ V {\displaystyle x\in V} , thêm cung ( s → v ) {\displaystyle (s\rightarrow v)} có trọng số w ( s → v ) = 0 {\displaystyle w(s\rightarrow v)=0}
Áp dụng thuật toán Bellman-Ford tìm khoảng cách ngắn nhất δ ( s , x ) {\displaystyle \delta (s,x)} từ s {\displaystyle s} tới mọi x ∈ V {\displaystyle x\in V} và sử dụng khoảng cách đó làm thế năng của đỉnh x {\displaystyle x} , i.e, p ( x ) = δ ( s , x ) {\displaystyle p(x)=\delta (s,x)}
Gán cho mỗi cung ( u → v ) ∈ E → {\displaystyle (u\rightarrow v)\in {\overrightarrow {E}}} một trọng số mới. △ ( u → v ) = w ( u → v ) + p ( u ) − p ( v ) {\displaystyle \vartriangle (u\rightarrow v)=w(u\rightarrow v)+p(u)-p(v)} . Gọi đồ thị với trọng số mới là H {\displaystyle H} ( H {\displaystyle H} là đồ thì có trọng số không âm)
Áp dụng Dijkstra V {\displaystyle V} lần cho đồ thị H {\displaystyle H} để tìm đường đi ngắn nhất giữa mọi cặp đỉnh trong H {\displaystyle H} . Gọi δ H ( x , y ) , δ ( x , y ) {\displaystyle \delta _{H}(x,y),\delta (x,y)} lần lượt là khoảng cách từ x {\displaystyle x} tơi y {\displaystyle y} trong H {\displaystyle H} và G {\displaystyle G} . độ lệch của đường đi ngắn nhất từ x {\displaystyle x} tới y {\displaystyle y} chính là δ ( x , y ) = δ H ( x , y ) + p ( y ) − p ( x ) {\textstyle \delta (x,y)=\delta _{H}(x,y)+p(y)-p(x)} Từ đó suy ra: δ ( x , y ) = δ H ( x , y ) + p ( y ) − p ( x ) {\textstyle \delta (x,y)=\delta _{H}(x,y)+p(y)-p(x)} .
Mô tả theo cách nông dân thì:
Thêm một đỉnh s {\displaystyle s} vào đồ thị G {\displaystyle G} , có cạnh đến bất kỳ đỉnh nào của G {\displaystyle G} cũng được và s {\displaystyle s} có trọng số là 0.(ở hình bên dưới là đỉnh q)
Dùng thuật toán Bellman-Ford, tìm đường đi từ s {\displaystyle s} đến các đỉnh còn lại. (kết quả được đồ thị thứ 2 ở hình bên dưới)
Thay đổi trọng số của đồ thị đã cho G {\displaystyle G} bằng đồ thị mới H {\displaystyle H} có trọng số không âm bằng cách, Mỗi cạnh từ u đến v có trọng số w ( u → v ) {\displaystyle w(u\rightarrow v)} thay bằng giá trị mới △ ( u → v ) = w ( u → v ) + p ( u ) − p ( v ) {\displaystyle \vartriangle (u\rightarrow v)=w(u\rightarrow v)+p(u)-p(v)} .(kết quả được đồ thị thứ 3 ở hình bên dưới)
Dùng thuật toán Dijsktra với đồ thị H {\displaystyle H}
